import codeJamUtils
import sys

def _find_best_flip_num(case):
    outletFlowStrs, deviceFlowStrs = case
    if (len(outletFlowStrs) == 0 or len(outletFlowStrs) != len(deviceFlowStrs)):
        return -1

    L = len(outletFlowStrs[0])

    # for each possible flip string, apply it to out outlet flows, and check that
    # each device str is present in the set. If they are, then the flip string is
    # feasible. Keep track of the best one seen so far

    minFlips = sys.maxsize

    # One approach: try every one of the possible 2^L strings i.e.:
    # for i in range(2**L):
    #
    # but to get faster, we can observe that since a given device (the first one, for
    # example, must be plugged into exacltly one of the outlets, we must chose a 
    # flip string that causes at least on of the outlets to match the first device's
    # flow!
    for i in (int(deviceFlowStrs[0], 2) ^ int(o, 2) for o in outletFlowStrs):
        if bin(i).count('1') >= minFlips:
            # only consider flip strings with fewer flips than the min found so far
            continue

        newOutletFlows = { i ^ int(outletFlowStr, 2) for outletFlowStr in outletFlowStrs } 
        isValid = True
        for deviceFlow in (int(deviceFlowStr, 2) for deviceFlowStr in deviceFlowStrs):
            if deviceFlow not in newOutletFlows:
                isValid = False
                break

        if isValid:
            minFlips = bin(i).count('1')

    if minFlips == sys.maxsize:
        return -1
    else:
        return minFlips


# If we wanted to generate the strings directly and didn't care about memory...
#def _generate_all_binary_strings(l):
#    allStrings = []
    
#    if l == 0:
#        return ['']

#    shorterStrings = _generate_all_binary_strings(l-1)
#    for s in shorterStrings:
#        allStrings.append(s + '0')
#        allStrings.append(s + '1')

#    return allStrings


def _parse_input(lines):
    numCases = int(lines[0])
    cases = []

    for i in range(numCases):

        outletFlowsStr = lines[3*i + 2]
        deviceFlowsStr = lines[3*i + 3]
        
        outletFlowStrs = str.split(outletFlowsStr)
        deviceFlowStrs = str.split(deviceFlowsStr)

        cases.append((outletFlowStrs, deviceFlowStrs))

    return cases

if __name__ == "__main__":
    testCases = _parse_input(codeJamUtils.get_input_lines("chargingChaos.txt"))
    for i, case in enumerate(testCases):
        bestFlipNum = _find_best_flip_num(case)
        output = str(bestFlipNum)
        if (bestFlipNum == -1):
            output = "NOT POSSIBLE"
        codeJamUtils.write_output("chargingChaos.txt", i + 1, output)